/*
题解链接:https://leetcode.cn/problems/count-good-triplets-in-an-array/description/?envType=daily-question&envId=2025-04-15
*/

//题解代码:
class Solution {
public:
    #define ll long long 
    #define N 100005
    int tree[N];
    void add(int i,int v){
        while(i<N){
            tree[i] += v;
            i += i&-i;
        }
    }
    int query(int i){
        int ret = 0;
        while(i>0){
            ret += tree[i];
            i -= i&-i;
        }
        return ret;
    }
    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        ll ans = 0;
        int n = nums1.size();
        vector<int> p(n);
        for(int i=0;i<n;++i){
            p[nums1[i]] = i;
        }
        for(int i=0;i<n;++i){
            nums2[i] = p[nums2[i]];
        }
        vector<int> left(n),right(n);
        for(int i=0;i<n;++i){
            left[i] = query(nums2[i]);
            add(nums2[i]+1,1);
        }
        memset(tree,0,sizeof(tree));
        for(int i=n-1;i>=0;--i){
            right[i] = (n-i-1) - query(nums2[i]+1);
            add(nums2[i]+1,1);
            ans += 1LL*left[i]*right[i];
        }
        return ans;
    }
};
